class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        // 下面是动态规划的解法，时间复杂度是O(N ^ 2)，空间复杂度是O(N)
        int n = nums.size();
        vector<int> f(n, 1);    // 上升
        vector<int> g(n, 1);    // 下降
        int ret = 1;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                    f[i] = max(g[j] + 1, f[i]);
                if(nums[i] < nums[j])
                    g[i] = max(f[j] + 1, g[i]);
            }
            ret = max(max(f[i], g[i]), ret);
        }
        return ret;

        // 下面是贪心解法，时间复杂度是O(N)
        // 贪心策略: 统计所有波峰和波谷
        // int i = 0, left = 0, right = 0, n = nums.size(), ret = 0;
        // // if(n < 2)
        // //     return n;
        // while(i < n - 1)
        // {
        //     right = nums[i + 1] - nums[i];
        //     i++;
        //     if(right == 0)
        //         continue;
            
        //     if(right * left <= 0)
        //         ret++;
        //     left = right;
            
        // }
        // return ret + 1;
    }
};